<?php
// https://mp.weixin.qq.com/s/yLc7-CZdti8gEMGWhd0JTg
// https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/
// https://mp.weixin.qq.com/s/1bzwER-LOB6a4HLkDbi8bQ
class Solution {
    /*
     * @param ListNode $head
     * @return Boolean
     */
    function detectCycle($head) {
        if ($head == null || $head->next == null) {
            return 0;
        }

        $slow = $fast = $head;

        // 我们使用两个指针，fast 与 slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。
        // 这里为什么不用判断 $fast->next->next == null ， 是因为$fast->next不为null $fast->next->next一定有值或者为null
        while ($fast != null && $fast->next != null) {
            $fast = $fast->next->next;
            $slow = $slow->next;
            if ($fast == $slow) {
                break;
            }
        }

        // 没有相遇点
        if ($fast == null) {
            return 0;
        }

        // 找到了 slow 与 fast 的相遇节点，令 solw 与 fast 指针从相遇节点出发，按照之前的前进规则，当 slow 与fast 再次相遇时，slow 走过的长度正好为环的长度
        $length = 1; // 环长度
        // 再次相遇
        while ($fast != $slow) {
            $fast = $fast->next->next;
            $slow = $slow->next;
            $length++;
        }

        return $length ;
    }
}

class ListNode {
    public $val = 0;
     public $next = null;
     function __construct($val) { $this->val = $val; }
 }